1. Technical Field of the Invention
This invention relates to communications protocols, and more particularly a system and method for exchanging routing information among gateways and hosts and local and wide area networks.
2. Background Art
The Routing Information Protocol (RIP) is a defacto standard for the exchange of routing information among gateways and hosts. Two such standards are the RIP-1 and RIP-2. RIP-1 is described in Network Working Group, Routing Information Protocol, Request for Comments (RFC) 1058, June 1988, pages 1-33. RIP-2 is described in Network Working Group, RIP Version 2 Carrying Additional Information, RFC 1723, November 1994, pages 1-9.
The Internet is organized into a number of networks connected by gateways. The networks may be either point-to-point links or more complex networks such as Ethernet or the ARPANET. Hosts and gateways are presented with IP datagrams addressed to some host. Routing is the method by which the host or gateway decides where to send the datagram. It may be able to send the datagram directly to the destination, if that destination is on one of the networks that are directly connected to the host or gateway. When the destination is not directly connected, and thus not directly reachable, the host or gateway attempts to send the datagram to a gateway that is nearer the destination. The goal of a routing protocol is to supply the information that is needed to do routing. (See Network Working Group, Routing Information Protocol, Request for Comments (RFC) 1058, June 1988, pp. 2-3.)
Routing is the task of finding a path from a sender to a desired destination. This may be viewed as a matter of finding gateways between networks. Internet protocol (IP) routing deals with communicating messages from a sender on one such network to a destination on a different one. In that case, the message must pass through gateways connecting the networks. If the networks are not adjacent, the message may pass through several intervening networks and the gateways connecting them. A "network" may cover a single broadcast network (e.g., an Ethernet), a point to point line, or the ARPANET. A network is treated as a single entity by IP. Either no routing is necessary (as with a point to point line), or routing is done in a manner transparent to IP, allowing IP to treat the entire network as a single full-connected system (as with Ethernet or the ARPANET.) When using the term "network" in connection with IP addressing, a single network number may be assigned to a collection of networks, with "subnet" addressing used to describe the individual networks.
One of several approaches for finding routes between networks is based on distance vector algorithms. In this approach, each entity (gateway or host) that participates in the routing protocol is assumed to keep in a routing database information about all of the destinations within the system. Each entry in this routing database includes the next gateway to which datagrams destined for the entity should be sent and a "metric" measuring the total distance to the entity. Distance is a generalized concept which may also cover the time delay in getting messages to the entity or the dollar cost of sending messages to it. Routing information is exchanged only among entities that are adjacent; that is, entities that share a common network.
A typical routing database implementation includes the following information about each destination:
address: in IP implementations, this will be the IP address of the host or network. PA1 gateway: the first gateway along the route to the destination. PA1 interface: the physical network which must be used to reach the first gateway. PA1 metric: a number, indicating the distance to the destination. PA1 timer: the amount of time since the entry was last updated.
This database is initialized with a description of the entities that are directly connected to the system. It is updated according to information received in messages from neighboring gateways. Each entity participating in the routing scheme sends update messages that describe the routing database as it currently exists in that entity. Optimal routes for the entire system may be maintained using only information obtained from neighboring entities.
Distance vector algorithms are based on a table giving the best route to every destination in the system. A metric is used to define "best". In simple networks it is common to use a metric that simply counts how many gateways a message must go through (sometimes referred to as the number of hops.) In more complex networks, a metric may be chosen to represent the total amount of delay the message suffers, the cost of sending it, or some other quantity which may be minimized. In each approach, the metric represents a sum of costs for individual hops.
A host or gateway G keeps, for each destination in the system a current estimate of the metric for that destination and the identity of the neighboring gateway on whose data that metric is based. If the destination is on a network that is directly connect to gateway G, then G uses an entry that shows the cost of using the network, and the fact that no gateway is needed to get to the destination. This combination of destination, metric, and gateway is typically referred to as a route to the destination with that metric, using that gateway.
Periodically, each gateway or host sends a routing update to every neighbor. The update is a set of messages that contain all of the information from the routing table. (The format of a RIP-1 message is shown in FIG. 3, and that of a RIP-2 message in FIG. 3.) It contains an entry for each destination, with the distance shown to that destination. When a routing update arrives from a neighbor G', this gateway G adds the cost associated with the network that is shared with G' (the network over which the update arrived), and the result compared with the current entry in this gateway's routing table for the destination. If the metric is less, the table entry is updated to the new metric and gateway.
It is an object of the invention to provide an improved method and system for operating a router in a RIP system while limiting the communication of datagrams through a particular gateway.
It is a further object of the invention to limit the communication of datagrams by way of a route through a particular gateway having a relatively lower metric to avoid overuse of a particular host by increasing usage of routes with higher metrics.
It is a further object of the invention to enable a router to support a RIP environment implementing a distance vector algorithm while restricting routes through that router.
It is an object of the invention to provide a method and system supporting a routing information protocol (RIP) based upon a least cost algorithm for exchanging routing information while restricting routes over wide area network interfaces.